/*
leetcode 56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 

提示：
1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {

    if (intervals.empty()) return {};

    // 按照每个区间的起始位置排序
    //传入了一个 lambda 函数来定义排序规则。lambda 函数的参数是两个区间 a 和 b，并通过 a[0] < b[0] 比较它们的起始位置。
    //sort 函数将按照这个规则将区间按起始位置升序排列。
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    vector<vector<int>> result;//定义二维向量，用于存储最终合并后的区间
    
    // 将第一个区间加入结果
    result.push_back(intervals[0]);

    //从排序后的第二个区间开始遍历所有区间
    for (int i = 1; i < intervals.size(); i++) {

        // 获取当前区间和结果中最后一个区间
        vector<int> &last = result.back();//result.back() 获取当前 result 中最后一个区间（即最右端的区间）
        vector<int> &curr = intervals[i];//intervals[i] 获取当前遍历的区间。我们通过引用获取这两个区间，以便直接修改它们。
        
        // 如果有重叠，更新结果中的最后一个区间
        //如果当前区间的起始位置 curr[0] 小于或等于 last 区间的结束位置 last[1]，说明这两个区间有重叠或相邻
        if (curr[0] <= last[1]) {
            last[1] = max(last[1], curr[1]);
           // result.back() = last; //如果不想使用用引用&的方式，则需要加这一行代码，使用 result.back() 更新最后一个区间
        } else {
            // 如果没有重叠，直接加入当前区间
            result.push_back(curr);
        }
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> merged = merge(intervals);
    
    for (const auto& interval : merged) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    
    return 0;
}

/*

输入示例：
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

步骤 1：排序区间
首先，我们对所有区间按照起始位置升序进行排序。排序后的结果是：
{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
排序的目的是让重叠的区间靠近，从而方便我们逐一进行合并。

步骤 2：初始化结果
初始化一个 result 向量，并将第一个区间 {1, 3} 放入其中：
result = {{1, 3}};

步骤 3：遍历区间
我们遍历排序后的 intervals，从第二个区间开始，逐一与 result 中的最后一个区间进行比较。

第一次迭代（i = 1）：
当前区间 curr = {2, 6}，result 中的最后一个区间 last = {1, 3}。
判断是否重叠：curr[0] (2) <= last[1] (3)，即 2 <= 3，成立，所以这两个区间有重叠。
合并：我们更新 last[1] = max(last[1], curr[1]) = max(3, 6) = 6，所以 last 被更新为 {1, 6}。
更新 result 中的最后一个区间：result.back() = last，所以 result 变为：
result = {{1, 6}};

第二次迭代（i = 2）：
当前区间 curr = {8, 10}，result 中的最后一个区间 last = {1, 6}。
判断是否重叠：curr[0] (8) <= last[1] (6)，即 8 <= 6，不成立，所以这两个区间没有重叠。
直接将当前区间 curr = {8, 10} 添加到 result 中：
result = {{1, 6}, {8, 10}};

第三次迭代（i = 3）：
当前区间 curr = {15, 18}，result 中的最后一个区间 last = {8, 10}。
判断是否重叠：curr[0] (15) <= last[1] (10)，即 15 <= 10，不成立，所以这两个区间没有重叠。
直接将当前区间 curr = {15, 18} 添加到 result 中：
result = {{1, 6}, {8, 10}, {15, 18}};

步骤 4：返回结果
遍历结束后，result 中存储的就是所有合并后的区间：

result = {{1, 6}, {8, 10}, {15, 18}};
因此，最终返回的结果是 {{1, 6}, {8, 10}, {15, 18}}，即合并后的区间。
*/